The present invention relates to hash tables. In particular, it relates to methods and systems for storing data in association with a key within a hash table and retrieving the data from the hash table using the key.
Hash tables (or hash maps) can be used to implement associative arrays (or maps or dictionaries) which store data (or values) in association with a key (i.e. as a key-value pair) such that each key is only used once. Hash tables make use of a hash function to compute an index into an array of buckets (or slots). In this way, for a given key, a bucket in which the data for that key should be stored can be identified by applying the hash function to the key. This may also be referred to as mapping the key to a bucket. Multiple different keys may map to the same bucket within a hash table. Therefore, hash tables are typically configured to store multiple key-value pairs or elements within each bucket. This means that, in addition to identifying the bucket in which data should be stored by applying the hash function, it may be necessary to search through the multiple elements within that bucket to find the element that corresponds to a particular key.
Hash tables may be used as a component of a variety of different systems. An example of a system which makes use of hash tables is a network element. Network elements, such as routers or switches, perform operations relative to packet flows that pass through them. Such network elements may use hash tables to store data relating to a particular packet flow in association with a key which identifies the packet flow. Typically, when a network element receives a packet, it performs packet classification to determine the identity of the packet flow by parsing specific fields within message headers such as MAC addresses, IP addresses and/or Tunnel Endpoint Identifiers (TEIDs). The network element may then retrieve the data about the relevant packet flow from the hash table by using a combination of the specific fields which identify the packet flow as a key. The network element may also (or alternatively) record information about the processing of the packet by writing data to the packet flow data stored in the hash table using the same key.